package com.mengfou.linklist;

import com.sun.org.apache.xpath.internal.objects.XNull;

import java.util.*;
import java.util.List;

/**
 * 拷贝链表
 * @author mengfou
 * 2022-1-10 09:50:29
 */
public class CopyLinkedList {
    static class NewNode {
        private int val;
        private NewNode next;
        private NewNode rand;

        public NewNode(int val) {
            this.val = val;
            this.next = null;
            this.rand = null;
        }

        /**
         * 初始化链表
         * @param nextArr 可以看作单链表的有序数组
         * @param randPair 下标对，比如[[0, 2]]
         * @return 链表NewNode
         */
        public static NewNode createLinkedList(int[] nextArr, List<int[]> randPair){
            if(nextArr == null || nextArr.length == 0) return null;
            Map<Integer, NewNode> maps = new HashMap<>();
            NewNode dummyNode = new NewNode(-1);
            NewNode ptr = dummyNode;
            int index = 0;
            for (int val : nextArr) {
                NewNode node = new NewNode(val);
                maps.put(index, node);
                ptr.next = node;
                ptr = ptr.next;
                index++;
            }
            ptr.next = null;
            // 初始化rand对
            for (int[] pair : randPair) {
                maps.get(pair[0]).rand = maps.get(pair[1]);
            }
            return dummyNode.next;
        }

        /**
         * 打印链表
         * @param head
         */
        public static void printLinkedList(NewNode head){
            NewNode ptr = head;
            while(ptr != null){
                System.out.print(ptr.val);
                if(ptr.rand != null){
                    System.out.print("[rand:"+ptr.rand.val+"]\t");
                } else{
                    System.out.print("\t");
                }
                ptr = ptr.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        List<int[]> pairs = new ArrayList<>();
        pairs.add(new int[]{0, 2}); // 1, 4
        pairs.add(new int[]{2, 3}); // 4, 3
        NewNode node = NewNode.createLinkedList(new int[]{1, 5, 4, 3, 2}, pairs);
        System.out.println("原链表：");
        NewNode.printLinkedList(node);
        NewNode newNode = new CopyLinkedList().copyLinkedList_2(node);
        System.out.println("拷贝链表：");
        NewNode.printLinkedList(newNode);
    }

    /**
     * 链表拷贝，将每个新节点链接到老节点的后面，然后再抽离
     * @param list 待拷贝链表
     * @return 新链表
     */
    public NewNode copyLinkedList_2(NewNode list) {
        if (list == null) return list;
        NewNode ptr = list;
        // 按照next信息，新建拷贝节点，并链接到原节点的后面
        while(ptr != null){
            NewNode qtr = ptr.next;
            NewNode temp = new NewNode(ptr.val);
            temp.next = ptr.next;
            ptr.next = temp;
            ptr = qtr;
        }
        // 成对遍历链表，然后保存对应的rand信息
        ptr = list;
        while(ptr != null){
            if(ptr.rand != null) {
                ptr.next.rand = ptr.rand.next;
            }
            ptr = ptr.next.next;
        }
        // 抽离新、旧链表
        ptr = list;
        NewNode dummyNode = new NewNode(-1);
        NewNode qtr = dummyNode;
        while(ptr != null){
            qtr.next = ptr.next;
            ptr.next = ptr.next.next;
            ptr = ptr.next;
            qtr = qtr.next;
        }
        return dummyNode.next;
    }


    /**
     * 链表拷贝，直接使用Map来存储老节点、新节点之间的对应关系即可。然后进行遍历映射
     * @param list 待拷贝链表
     * @return 新链表
     */
    public NewNode copyLinkedList_1(NewNode list){
        if(list == null) return list;
        // 存储老节点 -> 新节点
        Map<NewNode, NewNode> maps = new HashMap<>();
        NewNode ptr = list;
        while(ptr != null){
            maps.put(ptr, new NewNode(ptr.val));
            ptr = ptr.next;
        }
        ptr = list;
        while(ptr != null){
            maps.get(ptr).next = maps.get(ptr.next);
            maps.get(ptr).rand = maps.get(ptr.rand);
            ptr = ptr.next;
        }
        return maps.get(list);
    }
}
